package com.njupt.Array;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class FirstMissingPositive_41 {

    public int firstMissingPositive(int[] nums) {

//        if(nums.length ==1){
//            if(nums[0] <=0 || nums[0] >= 2){
//                return 1;
//            } else if(nums[0] == 1){
//                return nums[0] + 1;
//            }
//        }
//
//        Arrays.sort(nums);
//        for (int i = 0; i < nums.length - 1; i++) {
//            if (nums[i] <= 0) {
//                continue;
//            }
//            if (nums[i] > 1) {
//                return 1;
//            }
//
//            if (nums[i + 1] - nums[i] > 1) {
//                return nums[i] + 1;
//            }
//
//        }
//        return nums[nums.length - 1] + 1;

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int max = Integer.MIN_VALUE;
        for(int i = 0;i < nums.length; i++){
            if(nums[i] > max){
                max = nums[i];
            }
            map.putIfAbsent(nums[i],1);
        }
        if(max < 0){
            return 1;
        }
        for(int i = 1;i<=max;i++){
            if(map.get(i) == null){
                return i;
            }
        }
        return max + 1;
    }

    public static void main(String[] args) {
//        int[] nums = {1, 2, 0};
//        int[] nums = {3,4,-1,1};
//        int[] nums = {7,8,9,11,12};
//        int[] nums = {2};
        int[] nums = {-5};
        FirstMissingPositive_41 test = new FirstMissingPositive_41();
        System.out.println(test.firstMissingPositive(nums));
    }
}
